/*
 https://github.com/rsms/js-lru
 entry             entry             entry             entry        
 ______            ______            ______            ______       
 | head |.newer => |      |.newer => |      |.newer => | tail |      
 |  A   |          |  B   |          |  C   |          |  D   |      
 |______| <= older.|______| <= older.|______| <= older.|______|      
 
 removed  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  added 
 */
export function Cache(maxLength) {
    // 标识当前缓存数组的大小
    this.size = 0
    // 标识缓存数组能达到的最大长度
    this.limit = maxLength
    //  head（最不常用的项），tail（最常用的项）全部初始化为undefined

    this.head = this.tail = void 0
    this._keymap = {}
}

var cp = Cache.prototype

cp.put = function (key, value) {
    var entry = {
        key: key,
        value: value
    }
    this._keymap[key] = entry
    if (this.tail) {
        // 如果存在tail（缓存数组的长度不为0），将tail指向新的 entry
        this.tail.newer = entry
        entry.older = this.tail
    } else {
        // 如果缓存数组的长度为0，将head指向新的entry
        this.head = entry
    }
    this.tail = entry
    // 如果缓存数组达到上限，则先删除 head 指向的缓存对象
    /* istanbul ignore if */
    if (this.size === this.limit) {
        this.shift()
    } else {
        this.size++
    }
    return value
}

cp.shift = function () {
    /* istanbul ignore next */
    var entry = this.head
    /* istanbul ignore if */
    if (entry) {
        // 删除 head ，并改变指向
        this.head = this.head.newer
        // 同步更新 _keymap 里面的属性值
        this.head.older =
            entry.newer =
            entry.older =
            this._keymap[entry.key] =
            void 0
        delete this._keymap[entry.key] //#1029
        // 同步更新 缓存数组的长度
        this.size--
    }
}
cp.get = function (key) {
    var entry = this._keymap[key]
    // 如果查找不到含有`key`这个属性的缓存对象
    if (entry === void 0)
        return
    // 如果查找到的缓存对象已经是 tail (最近使用过的)
    /* istanbul ignore if */
    if (entry === this.tail) {
        return entry.value
    }
    // HEAD--------------TAIL
    //   <.older   .newer>
    //  <--- add direction --
    //   A  B  C  <D>  E
    if (entry.newer) {
        // 处理 newer 指向
        if (entry === this.head) {
            // 如果查找到的缓存对象是 head (最近最少使用过的)
            // 则将 head 指向原 head 的 newer 所指向的缓存对象
            this.head = entry.newer
        }
        // 将所查找的缓存对象的下一级的 older 指向所查找的缓存对象的older所指向的值
        // 例如：A B C D E
        // 如果查找到的是D，那么将E指向C，不再指向D
        entry.newer.older = entry.older // C <-- E.
    }
    if (entry.older) {
        // 处理 older 指向
        // 如果查找到的是D，那么C指向E，不再指向D
        entry.older.newer = entry.newer // C. --> E
    }
    // 处理所查找到的对象的 newer 以及 older 指向
    entry.newer = void 0 // D --x
    // older指向之前使用过的变量，即D指向E
    entry.older = this.tail // D. --> E
    if (this.tail) {
        // 将E的newer指向D
        this.tail.newer = entry // E. <-- D
    }
    // 改变 tail 为D 
    this.tail = entry
    return entry.value
}


